home *** CD-ROM | disk | FTP | other *** search
/ Chip 2007 January, February, March & April / Chip-Cover-CD-2007-02.iso / Pakiet bezpieczenstwa / mini Pentoo LiveCD 2006.1 / mpentoo-2006.1.iso / livecd.squashfs / usr / lib / mozilla-firefox / include / xpcom / nsTHashtable.h < prev    next >
C/C++ Source or Header  |  2006-05-08  |  14KB  |  430 lines
  1. /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
  2. /* ***** BEGIN LICENSE BLOCK *****
  3.  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
  4.  *
  5.  * The contents of this file are subject to the Mozilla Public License Version
  6.  * 1.1 (the "License"); you may not use this file except in compliance with
  7.  * the License. You may obtain a copy of the License at
  8.  * http://www.mozilla.org/MPL/
  9.  *
  10.  * Software distributed under the License is distributed on an "AS IS" basis,
  11.  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  12.  * for the specific language governing rights and limitations under the
  13.  * License.
  14.  *
  15.  * The Original Code is C++ hashtable templates.
  16.  *
  17.  * The Initial Developer of the Original Code is
  18.  * Benjamin Smedberg.
  19.  * Portions created by the Initial Developer are Copyright (C) 2002
  20.  * the Initial Developer. All Rights Reserved.
  21.  *
  22.  * Contributor(s):
  23.  *
  24.  * Alternatively, the contents of this file may be used under the terms of
  25.  * either the GNU General Public License Version 2 or later (the "GPL"), or
  26.  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  27.  * in which case the provisions of the GPL or the LGPL are applicable instead
  28.  * of those above. If you wish to allow use of your version of this file only
  29.  * under the terms of either the GPL or the LGPL, and not to allow others to
  30.  * use your version of this file under the terms of the MPL, indicate your
  31.  * decision by deleting the provisions above and replace them with the notice
  32.  * and other provisions required by the GPL or the LGPL. If you do not delete
  33.  * the provisions above, a recipient may use your version of this file under
  34.  * the terms of any one of the MPL, the GPL or the LGPL.
  35.  *
  36.  * ***** END LICENSE BLOCK ***** */
  37.  
  38. #ifndef nsTHashtable_h__
  39. #define nsTHashtable_h__
  40.  
  41. #include "nscore.h"
  42. #include "pldhash.h"
  43. #include "nsDebug.h"
  44. #include NEW_H
  45.  
  46. // helper function for nsTHashtable::Clear()
  47. PR_EXTERN(PLDHashOperator) PR_CALLBACK
  48. PL_DHashStubEnumRemove(PLDHashTable    *table,
  49.                        PLDHashEntryHdr *entry,
  50.                        PRUint32         ordinal,
  51.                        void            *userArg);
  52.  
  53.  
  54. /**
  55.  * a base class for templated hashtables.
  56.  *
  57.  * Clients will rarely need to use this class directly. Check the derived
  58.  * classes first, to see if they will meet your needs.
  59.  *
  60.  * @param EntryType  the templated entry-type class that is managed by the
  61.  *   hashtable. <code>EntryType</code> must extend the following declaration,
  62.  *   and <strong>must not declare any virtual functions or derive from classes
  63.  *   with virtual functions.</strong>  Any vtable pointer would break the
  64.  *   PLDHashTable code.
  65.  *<pre>   class EntryType : public PLDHashEntryHdr
  66.  *   {
  67.  *   public: or friend nsTHashtable<EntryType>;
  68.  *     // KeyType is what we use when Get()ing or Put()ing this entry
  69.  *     // this should either be a simple datatype (PRUint32, nsISupports*) or
  70.  *     // a const reference (const nsAString&)
  71.  *     typedef something KeyType;
  72.  *     // KeyTypePointer is the pointer-version of KeyType, because pldhash.h
  73.  *     // requires keys to cast to <code>const void*</code>
  74.  *     typedef const something* KeyTypePointer;
  75.  *
  76.  *     EntryType(KeyTypePointer aKey);
  77.  *
  78.  *     // the copy constructor must be defined, even if AllowMemMove() == true
  79.  *     // or you will cause link errors!
  80.  *     EntryType(const EntryType& aEnt);
  81.  *
  82.  *     // the destructor must be defined... or you will cause link errors!
  83.  *     ~EntryType();
  84.  *
  85.  *     // return the key of this entry
  86.  *     const KeyTypePointer GetKeyPointer() const;
  87.  *
  88.  *     // KeyEquals(): does this entry match this key?
  89.  *     PRBool KeyEquals(KeyTypePointer aKey) const;
  90.  *
  91.  *     // KeyToPointer(): Convert KeyType to KeyTypePointer
  92.  *     static KeyTypePointer KeyToPointer(KeyType aKey);
  93.  *
  94.  *     // HashKey(): calculate the hash number
  95.  *     static PLDHashNumber HashKey(KeyTypePointer aKey);
  96.  *
  97.  *     // ALLOW_MEMMOVE can we move this class with memmove(), or do we have
  98.  *     // to use the copy constructor?
  99.  *     enum { ALLOW_MEMMOVE = PR_(TRUE or FALSE) };
  100.  *   }</pre>
  101.  *
  102.  * @see nsInterfaceHashtable
  103.  * @see nsDataHashtable
  104.  * @see nsClassHashtable
  105.  * @author "Benjamin Smedberg <bsmedberg@covad.net>"
  106.  */
  107.  
  108. template<class EntryType>
  109. class nsTHashtable
  110. {
  111. public:
  112.   /**
  113.    * A dummy constructor; you must call Init() before using this class.
  114.    */
  115.   nsTHashtable();
  116.  
  117.   /**
  118.    * destructor, cleans up and deallocates
  119.    */
  120.   ~nsTHashtable();
  121.  
  122.   /**
  123.    * Initialize the table.  This function must be called before any other
  124.    * class operations.  This can fail due to OOM conditions.
  125.    * @param initSize the initial number of buckets in the hashtable, default 16
  126.    * @return PR_TRUE if the class was initialized properly.
  127.    */
  128.   PRBool Init(PRUint32 initSize = PL_DHASH_MIN_SIZE);
  129.  
  130.   /**
  131.    * Check whether the table has been initialized. This can be useful for static hashtables.
  132.    * @return the initialization state of the class.
  133.    */
  134.   PRBool IsInitialized() const { return mTable.entrySize; }
  135.  
  136.   /**
  137.    * KeyType is typedef'ed for ease of use.
  138.    */
  139.   typedef typename EntryType::KeyType KeyType;
  140.  
  141.   /**
  142.    * KeyTypePointer is typedef'ed for ease of use.
  143.    */
  144.   typedef typename EntryType::KeyTypePointer KeyTypePointer;
  145.  
  146.   /**
  147.    * Return the number of entries in the table.
  148.    * @return    number of entries
  149.    */
  150.   PRUint32 Count() const { return mTable.entryCount; }
  151.  
  152.   /**
  153.    * Get the entry associated with a key.
  154.    * @param     aKey the key to retrieve
  155.    * @return    pointer to the entry class, if the key exists; nsnull if the
  156.    *            key doesn't exist
  157.    */
  158.   EntryType* GetEntry(KeyType aKey) const
  159.   {
  160.     NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");
  161.   
  162.     EntryType* entry =
  163.       NS_REINTERPRET_CAST(EntryType*,
  164.                           PL_DHashTableOperate(
  165.                             NS_CONST_CAST(PLDHashTable*,&mTable),
  166.                             EntryType::KeyToPointer(aKey),
  167.                             PL_DHASH_LOOKUP));
  168.     return PL_DHASH_ENTRY_IS_BUSY(entry) ? entry : nsnull;
  169.   }
  170.  
  171.   /**
  172.    * Get the entry associated with a key, or create a new entry,
  173.    * @param     aKey the key to retrieve
  174.    * @return    pointer to the entry class retreived; nsnull only if memory
  175.                 can't be allocated
  176.    */
  177.   EntryType* PutEntry(KeyType aKey)
  178.   {
  179.     NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");
  180.     
  181.     return NS_STATIC_CAST(EntryType*,
  182.                           PL_DHashTableOperate(
  183.                             &mTable,
  184.                             EntryType::KeyToPointer(aKey),
  185.                             PL_DHASH_ADD));
  186.   }
  187.  
  188.   /**
  189.    * Remove the entry associated with a key.
  190.    * @param     aKey of the entry to remove
  191.    */
  192.   void RemoveEntry(KeyType aKey)
  193.   {
  194.     NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");
  195.  
  196.     PL_DHashTableOperate(&mTable,
  197.                          EntryType::KeyToPointer(aKey),
  198.                          PL_DHASH_REMOVE);
  199.   }
  200.  
  201.   /**
  202.    * Remove the entry associated with a key, but don't resize the hashtable.
  203.    * This is a low-level method, and is not recommended unless you know what
  204.    * you're doing and you need the extra performance. This method can be used
  205.    * during enumeration, while RemoveEntry() cannot.
  206.    * @param aEntry   the entry-pointer to remove (obtained from GetEntry or
  207.    *                 the enumerator
  208.    */
  209.   void RawRemoveEntry(EntryType* aEntry)
  210.   {
  211.     PL_DHashTableRawRemove(&mTable, aEntry);
  212.   }
  213.  
  214.   /**
  215.    * client must provide an <code>Enumerator</code> function for
  216.    *   EnumerateEntries
  217.    * @param     aEntry the entry being enumerated
  218.    * @param     userArg passed unchanged from <code>EnumerateEntries</code>
  219.    * @return    combination of flags
  220.    *            @link PLDHashOperator::PL_DHASH_NEXT PL_DHASH_NEXT @endlink ,
  221.    *            @link PLDHashOperator::PL_DHASH_STOP PL_DHASH_STOP @endlink ,
  222.    *            @link PLDHashOperator::PL_DHASH_REMOVE PL_DHASH_REMOVE @endlink
  223.    */
  224.   typedef PLDHashOperator (*PR_CALLBACK Enumerator)(EntryType* aEntry, void* userArg);
  225.  
  226.   /**
  227.    * Enumerate all the entries of the function.
  228.    * @param     enumFunc the <code>Enumerator</code> function to call
  229.    * @param     userArg a pointer to pass to the
  230.    *            <code>Enumerator</code> function
  231.    * @return    the number of entries actually enumerated
  232.    */
  233.   PRUint32 EnumerateEntries(Enumerator enumFunc, void* userArg)
  234.   {
  235.     NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");
  236.     
  237.     s_EnumArgs args = { enumFunc, userArg };
  238.     return PL_DHashTableEnumerate(&mTable, s_EnumStub, &args);
  239.   }
  240.  
  241.   /**
  242.    * remove all entries, return hashtable to "pristine" state ;)
  243.    */
  244.   void Clear()
  245.   {
  246.     NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");
  247.  
  248.     PL_DHashTableEnumerate(&mTable, PL_DHashStubEnumRemove, nsnull);
  249.   }
  250.  
  251. protected:
  252.   PLDHashTable mTable;
  253.  
  254.   static const void* PR_CALLBACK s_GetKey(PLDHashTable    *table,
  255.                                           PLDHashEntryHdr *entry);
  256.  
  257.   static PLDHashNumber PR_CALLBACK s_HashKey(PLDHashTable *table,
  258.                                              const void   *key);
  259.  
  260.   static PRBool PR_CALLBACK s_MatchEntry(PLDHashTable           *table,
  261.                                          const PLDHashEntryHdr  *entry,
  262.                                          const void             *key);
  263.   
  264.   static void PR_CALLBACK s_CopyEntry(PLDHashTable          *table,
  265.                                       const PLDHashEntryHdr *from,
  266.                                       PLDHashEntryHdr       *to);
  267.   
  268.   static void PR_CALLBACK s_ClearEntry(PLDHashTable *table,
  269.                                        PLDHashEntryHdr *entry);
  270.  
  271.   static PRBool PR_CALLBACK s_InitEntry(PLDHashTable     *table,
  272.                                         PLDHashEntryHdr  *entry,
  273.                                         const void       *key);
  274.  
  275.   /**
  276.    * passed internally during enumeration.  Allocated on the stack.
  277.    *
  278.    * @param userFunc the Enumerator function passed to
  279.    *   EnumerateEntries by the client
  280.    * @param userArg the userArg passed unaltered
  281.    */
  282.   struct s_EnumArgs
  283.   {
  284.     Enumerator userFunc;
  285.     void* userArg;
  286.   };
  287.   
  288.   static PLDHashOperator PR_CALLBACK s_EnumStub(PLDHashTable    *table,
  289.                                                 PLDHashEntryHdr *entry,
  290.                                                 PRUint32         number,
  291.                                                 void            *arg);
  292. private:
  293.   // copy constructor, not implemented
  294.   nsTHashtable(nsTHashtable<EntryType>& toCopy);
  295.  
  296.   // assignment operator, not implemented
  297.   nsTHashtable<EntryType>& operator= (nsTHashtable<EntryType>& toEqual);
  298. };
  299.  
  300. //
  301. // template definitions
  302. //
  303.  
  304. template<class EntryType>
  305. nsTHashtable<EntryType>::nsTHashtable()
  306. {
  307.   // entrySize is our "I'm initialized" indicator
  308.   mTable.entrySize = 0;
  309. }
  310.  
  311. template<class EntryType>
  312. nsTHashtable<EntryType>::~nsTHashtable()
  313. {
  314.   if (mTable.entrySize)
  315.     PL_DHashTableFinish(&mTable);
  316. }
  317.  
  318. template<class EntryType>
  319. PRBool
  320. nsTHashtable<EntryType>::Init(PRUint32 initSize)
  321. {
  322.   if (mTable.entrySize)
  323.   {
  324.     NS_ERROR("nsTHashtable::Init() should not be called twice.");
  325.     return PR_TRUE;
  326.   }
  327.  
  328.   static PLDHashTableOps sOps = 
  329.   {
  330.     ::PL_DHashAllocTable,
  331.     ::PL_DHashFreeTable,
  332.     s_GetKey,
  333.     s_HashKey,
  334.     s_MatchEntry,
  335.     ::PL_DHashMoveEntryStub,
  336.     s_ClearEntry,
  337.     ::PL_DHashFinalizeStub,
  338.     s_InitEntry
  339.   };
  340.  
  341.   if (!EntryType::ALLOW_MEMMOVE)
  342.   {
  343.     sOps.moveEntry = s_CopyEntry;
  344.   }
  345.   
  346.   if (!PL_DHashTableInit(&mTable, &sOps, nsnull, sizeof(EntryType), initSize))
  347.   {
  348.     // if failed, reset "flag"
  349.     mTable.entrySize = 0;
  350.     return PR_FALSE;
  351.   }
  352.  
  353.   return PR_TRUE;
  354. }
  355.  
  356. // static definitions
  357.  
  358. template<class EntryType>
  359. const void*
  360. nsTHashtable<EntryType>::s_GetKey(PLDHashTable    *table,
  361.                                   PLDHashEntryHdr *entry)
  362. {
  363.   return ((EntryType*) entry)->GetKeyPointer();
  364. }
  365.  
  366. template<class EntryType>
  367. PLDHashNumber
  368. nsTHashtable<EntryType>::s_HashKey(PLDHashTable  *table,
  369.                                    const void    *key)
  370. {
  371.   return EntryType::HashKey(NS_REINTERPRET_CAST(const KeyTypePointer, key));
  372. }
  373.  
  374. template<class EntryType>
  375. PRBool
  376. nsTHashtable<EntryType>::s_MatchEntry(PLDHashTable          *table,
  377.                                       const PLDHashEntryHdr *entry,
  378.                                       const void            *key)
  379. {
  380.   return ((const EntryType*) entry)->KeyEquals(
  381.     NS_REINTERPRET_CAST(const KeyTypePointer, key));
  382. }
  383.  
  384. template<class EntryType>
  385. void
  386. nsTHashtable<EntryType>::s_CopyEntry(PLDHashTable          *table,
  387.                                      const PLDHashEntryHdr *from,
  388.                                      PLDHashEntryHdr       *to)
  389. {
  390.   EntryType* fromEntry =
  391.     NS_CONST_CAST(EntryType*, NS_REINTERPRET_CAST(const EntryType*, from));
  392.  
  393.   new(to) EntryType(*fromEntry);
  394.  
  395.   fromEntry->~EntryType();
  396. }
  397.  
  398. template<class EntryType>
  399. void
  400. nsTHashtable<EntryType>::s_ClearEntry(PLDHashTable    *table,
  401.                                       PLDHashEntryHdr *entry)
  402. {
  403.   NS_REINTERPRET_CAST(EntryType*,entry)->~EntryType();
  404. }
  405.  
  406. template<class EntryType>
  407. PRBool
  408. nsTHashtable<EntryType>::s_InitEntry(PLDHashTable    *table,
  409.                                      PLDHashEntryHdr *entry,
  410.                                      const void      *key)
  411. {
  412.   new(entry) EntryType(NS_REINTERPRET_CAST(KeyTypePointer,key));
  413.   return PR_TRUE;
  414. }
  415.  
  416. template<class EntryType>
  417. PLDHashOperator
  418. nsTHashtable<EntryType>::s_EnumStub(PLDHashTable    *table,
  419.                                     PLDHashEntryHdr *entry,
  420.                                     PRUint32         number,
  421.                                     void            *arg)
  422. {
  423.   // dereferences the function-pointer to the user's enumeration function
  424.   return (* NS_REINTERPRET_CAST(s_EnumArgs*,arg)->userFunc)(
  425.     NS_REINTERPRET_CAST(EntryType*,entry),
  426.     NS_REINTERPRET_CAST(s_EnumArgs*,arg)->userArg);
  427. }
  428.  
  429. #endif // nsTHashtable_h__
  430.